﻿//// 消除整数
//// https://ac.nowcoder.com/acm/problem/219038
//
//#include <iostream>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <functional>
//#include <climits>
//#include <cstring>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//// 我的写法，模拟手算
//void solve1()
//{
//    int x;
//    cin >> x;
//
//    int ans = 1;// 因为第一次永远减1
//    x--;
//
//    ans += x % 2;// 贪心，因为后面都是像扩二倍来减少次数，先把奇数的影响去除
//    x -= (x % 2);
//
//    int c = 2;
//    while (x / c)
//    {
//        ans++;
//        x -= c;
//        c *= 2;// 2 4 8，看能够几次
//    }
//    while (x)// 看2 2 4这种情况
//    {
//        c /= 2;
//        while (x / c)
//        {
//            ans++;
//            x -= c;
//        }
//    }
//    cout << ans << endl;
//}
//
//// 老师写法：
//// 贪⼼ + 数学。
//// a. 尽可能的翻倍；
//// b. 不能⽆脑翻倍，只能是 2 * cur 的倍数时，才能翻倍。
//void solve()
//{
//    int n, ans = 0;
//    cin >> n;
//    int c = 1;
//    while (n)
//    {
//        ans++;
//        n -= c;
//        if (n % (c * 2) == 0)
//            c *= 2;
//    }
//    cout << ans << endl;
//}
//
//int main()
//{
//    int t;
//    cin >> t;
//    while (t--)
//        solve();
//    return 0;
//}
//
//
// 
//// NC164 最长上升子序列(二)
//// https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237?tpId=196&tqId=39285&ru=/exam/oj
//
//const int N = 1e5 + 1;
//int dp[N];// 存子序列长度为i的结尾值
//
//class Solution {
//public:
//    int LIS(vector<int>& a)
//    {
//        int sz = a.size(), l, r, mid;
//        for (int i = 0; i < sz; i++)
//        {
//            l = 0, r = len;
//            while (l < r)
//            {
//                // mid = l + ((r - l + 1) >> 1);
//                mid = (l + r + 1) / 2;
//                if (dp[mid] < a[i])
//                    l = mid;
//                else
//                    r = mid - 1;
//            }
//            len = max(len, l + 1);
//            dp[l + 1] = a[i];
//        }
//
//        return len;
//    }
//private:
//    int len = 0;
//};
//
//int main()
//{
//    vector<int>v = { 1,4,7,5,6 };
//    Solution().LIS(v);
//    return 0;
//}
//// 排序子序列
//// https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471
//
//// 注意题意！！！！！！！！！1
//// 它是将数组分段，让他每一段都是非递增或者非递减，是离散图，不是函数图
//// 如样例：1 2 3 2 2 1
//// 是分为1 2 3， 2 2 1
//// 不是：1 2 3， 3 2 2 1
//// 也就是说一个点不是共用的，不是同时组成两段
//
//#include <iostream>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <functional>
//#include <climits>
//#include <cstring>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//const int N = 1e5;
//
//int n;
//int a[N];
//
//// 错误写法，为连续型的答案
//void solve1()
//{
//    int flag = -1, ans = 1;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i];
//        if (i && a[i] > a[i - 1])
//        {
//            if (flag != -1 && flag == 2)
//                ans++;
//            flag = 1;
//        }
//        else if (i && a[i] < a[i - 1])
//        {
//            if (flag != -1 && flag == 1)
//                ans++;
//            flag = 2;
//        }
//    }
//    if (flag == -1)
//        cout << 1 << endl;
//    else
//        cout << ans << endl;
//}
//
//// 离散型的写法
//// 贪心：如果是上升的，就让它上升到最大，      下降 ，    下降      小, i++, ans++；如果遇见的平的，i++, ans不变
//void solve()
//{
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i];
//    }
//
//    int ans = 0;
//    for (int i = 0; i < n - 1;)
//    {
//        if (a[i + 1] > a[i])
//        {
//            while (i < n - 1 && a[i + 1] >= a[i])
//                i++;
//            ans++;
//        }
//        else if (a[i + 1] < a[i])
//        {
//            while (i < n - 1 && a[i + 1] <= a[i])
//                i++;
//            ans++;
//        }
//        else
//        {
//            while (i < n - 1 && a[i + 1] == a[i])
//                i++;
//        }
//        i++;
//        if (i == n - 1)
//        {
//            ans++;
//            break;
//        }
//    }
//
//    cout << ans << endl;
//}
//
//int main()
//{
//    cin >> n;
//    if (n == 1)
//        cout << 1;
//    else
//        solve();
//    return 0;
//}